package librairies.arborescence.arbre;

import librairies.arborescence.interfaces.IArbre;
import librairies.exception.ArbreCyclique;
import librairies.exception.GreffeDeSousArbre;
import librairies.exception.SousArbreIncoherent;
import librairies.liste.interfaces.IListe;
import librairies.liste.list.ListeDC;

/**
 * Representation DC d'un arbre.
 * 
 * @author mlozach
 * @param <E> type de l'element dans l'arbre
 */
public class ArbreDC<E> implements IArbre<E> 
{
	private ArbreDC<E> father;
	private IListe<ArbreDC<E>> children;
	private E value;

	/**
	 * constructeur par recopie
	 * @param e le valeur du premier noeud
	 */
	public ArbreDC(E e) 
	{
		this.father = null;
		this.children = new ListeDC<ArbreDC<E>>();
		this.value = e;
	}

	/**
	 * permet de cree des suite de char
	 * @param c le caractere a cloner x fois
	 * @param i le nombre de repetition
	 * @return le string des chars
	 */
	private String seqChar(char c, int i) 
	{
		String res = "";
		
		for ( ; i > 0; i--)
		{
			res += c;
		}
		
		return res;
	}

	/**
	 * permet d'afficher proprement l'arbre.
	 * @param a l'arbre a afficher
	 * @return la liste des niveaux
	 */
	private <F> IListe<String> niveaux(IArbre<F> a) 
	{
		if(a == null) return new ListeDC<String>();
		
		String etiq = a.getVal().toString();
		
		if (a.isLeaf())
		{
			IListe<String> l = new ListeDC<String>();
			l.add(etiq);
			
			return new ListeDC<String>(l);
		}
		
		IListe<String> res = niveaux(a.children().get(0));
		String traits = (a.children().size() == 1 ? "|" : "+");
		int largeurTrait = res.get(0).length();
		
		for (int i = 1; i < a.children().size(); i++) 
		{
			int largeur1 = res.get(0).length();
			IListe<String> afusionner = niveaux(a.children().get(i));
			int largeur2 = afusionner.get(0).length();
			traits += seqChar('-', largeurTrait) + "+";
			
			for (int k = 0; k < res.size() && k < afusionner.size(); k++)
			{
				res.set(k, res.get(k) + " " + afusionner.get(k));
			}
			
			for (int k = res.size(); k < afusionner.size(); k++)
			{
				res.add(k, seqChar(' ', largeur1 + 1) + afusionner.get(k));
			}
			
			for (int k = afusionner.size(); k < res.size(); k++)
			{
				res.set(k, res.get(k) + seqChar(' ', largeur2 + 1));
			}
			
			largeurTrait = largeur2;
		}
		
		traits += seqChar(' ', res.get(res.size() - 1).length()-traits.length());
		res.add(0, traits).add(0, etiq+seqChar(' ', res.get(res.size()-1).length()-etiq.length()));
		
		return res;
	}
	
	@Override
	public E setVal(E e) 
	{
		E bak = this.value;
		this.value = e;
		
		return bak;
	}

	@Override
	public int familySize() 
	{
		int res = this.children.size();
		
		for (int i = 0; i < this.children.size(); i++)
		{
			res += this.children.get(i).familySize();
		}
		
		return res;
	}

	@Override
	public int height() 
	{
		int max = 0;
		
		for (int i = 0; i < this.children.size(); i++) 
		{
			int candidat = this.children.get(i).height() + 1;
			
			if (candidat > max)
			{
				max = candidat;
			}
		}
		
		return max;
	}
	
	@Override
	public IArbre<E> ancestor() 
	{ 
		if (this.father == null)
		{
			return null;
		}
		
		ArbreDC<E> aieul = this.father;
		
		while(aieul.father!=null) aieul=aieul.father;
		
		return aieul; 
	}
	
	@Override
	public IListe<? extends IArbre<E>> ancestors() 
	{
		IListe<IArbre<E>> res = new ListeDC<IArbre<E>>();
		
		for (ArbreDC<E> aieul = this.father; aieul != null; aieul = aieul.father) 
		{
			res.add(0, aieul);
		}
		
		return res;	
	}

	@Override
	public IListe<? extends IArbre<E>> brothers() 
	{
		IListe<IArbre<E>> res = new ListeDC<IArbre<E>>();
		
		if (this.father != null)
		{
			for (int i = 0; i < this.father.children.size(); i++) 
			{
				IArbre<E> candidat = this.father.children.get(i);
				
				if (this!=candidat)
				{
					res.add(candidat);
				}
			}
		}
		
		return res;
	}

	@Override
	public IListe<? extends IArbre<E>> gen(int n) 
	{
		if (n == 1)
		{
			return this.children;
		}
		
		IListe<IArbre<E>> res = new ListeDC<IArbre<E>>();
		
		if (n < 1)
		{
			return res;
		}
		
		for (int i = 0; i < this.children.size(); i++)
		{
			res.addAll(this.children.get(i).gen(n - 1));
		}
		
		return res;
	}

	@Override
	public boolean contains(IArbre<E> a) 
	{
		if(a == null)
		{
			return false;
		}
		
		if (a == this)
		{
			return true;
		}
		
		for (int i = 0; i < this.children.size(); i++)
		{
			if (this.children.get(i).contains(a))
			{
				return true;
			}
		}
		
		return false;
	}

	@Override
	public IListe<? extends IArbre<E>> cutAll() 
	{
		IListe<IArbre<E>> res = new ListeDC<IArbre<E>>();
		
		while (this.children.size() != 0)
		{
			res.add(cutChild(0));
		}
		
		return res;
	}

	@Override
	public IArbre<E> cutChild(int i) throws IndexOutOfBoundsException
	{
		if (i < 0 || i >= this.children.size())
		{
			throw new IndexOutOfBoundsException();
		}
		
		ArbreDC<E> res = this.children.remove(i);
		res.father = null;
		
		return res;
	}

	@Override
	public ArbreDC<E> getChild(int i) throws IndexOutOfBoundsException 
	{
		if (i < 0 || i >= this.children.size())
		{
			throw new IndexOutOfBoundsException();
		}
		
		return this.children.get(i);
	}

	@Override
	public IArbre<E> addChild(IArbre<E> a) throws NullPointerException,
			ArbreCyclique, GreffeDeSousArbre, SousArbreIncoherent 
	{
		if (a == null)
		{
			throw new NullPointerException();
		}

		ArbreDC<E> al = (ArbreDC<E>) a;
		
		if (al.father != null)
		{
			throw new GreffeDeSousArbre();
		}
		
		if (al.contains(this))
		{
			throw new ArbreCyclique();
		}
		
		return addChild(this.children.size(), a);		
	}
	
	@Override
	public IArbre<E> addChild(int i, IArbre<E> a) throws NullPointerException,
			IndexOutOfBoundsException, ArbreCyclique, GreffeDeSousArbre, SousArbreIncoherent 
	{
		if (a == null)
		{
			throw new NullPointerException();
		}
		
		if (i < 0 || i > this.children.size())
		{
			throw new IndexOutOfBoundsException();
		}
		
		ArbreDC<E> al;
		try 
		{ 
			al = (ArbreDC<E>) a; 
		}
		catch(ClassCastException e) 
		{ 
			throw new SousArbreIncoherent(); 
		}
		
		if (al.father != null) 
		{
			throw new GreffeDeSousArbre();
		}
		
		if (al.contains(this)) 
		{
			throw new ArbreCyclique();
		}
		
		al.father = this;
		this.children.add(i, al);
		
		return this;
	}
	
	@Override
	public IListe<E> prefixe() 
	{
		IListe<E> res = new ListeDC<E>().add(this.value);
		
		for (int i = 0; i < this.children.size(); i++) 
		{
			res.addAll(this.children.get(i).prefixe());
		}
		
		return res;
	}

	@Override
	public IListe<E> postfixe() 
	{
		IListe<E> res = new ListeDC<E>();
		
		for (int i = 0; i < this.children.size(); i++)
		{ 
			res.addAll(this.children.get(i).postfixe());
		}
		
		return res.add(this.value);
	}

	@Override
	public IListe<E> largeur() 
	{
		IListe<E> res = new ListeDC<E>().add(this.value);
		int height = height();
		
		for (int n = 1; n <= height; n++) 
		{
			IListe<? extends IArbre<E>> niveaux = gen(n);
			
			for (int i = 0; i < niveaux.size(); i++)
			{ 
				res.add(niveaux.get(i).getVal());
			}
		}
		
		return res;
	}

	@Override
	public E getVal() {return this.value;}
	@Override
	public boolean isLeaf() {return this.children.size()==0;}
	@Override
	public IArbre<E> father() {return this.father;}
	@Override
	public IListe<? extends IArbre<E>> children(){return this.children;}
	
	/**
	 * Methode object
	 */
	public String toString() 
	{
		IListe<String> niveaux = niveaux(this);
		String res = "";
		
		for (int i = 0; i < niveaux.size(); i++)
		{
			res += niveaux.get(i) + "\n";
		}
		
		return res;
	}
}